#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

int findMin(vector<int>& nums) 
{
  int down = 0;
  int top = nums.size()-1;
  int mid = 0;
  int ret=0;
  if( top<2 )
    return 0;

  if(nums[0]<nums.back())
    return nums[0];
  if( nums[0]>nums.back() && nums[top-1]>nums.back() )
    return nums.back();

  while(down<=top)
  {
    mid = (down+top)/2;
    if(nums[mid]>=nums[0])
      down = mid+1;
    else
      top = mid-1;
   
  }
  cout << "mid:"<<mid<<endl;

  return nums[mid]>=nums[0]?nums[mid+1]:nums[mid];

}



int main(int argc,char *argv[])
{
  vector<int> nums = {4,5,1,2,3};

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  int ret = findMin( nums );

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;


  cout << ret<<endl;



  return 0;
}
